Version francaise:

Universalité, inclusion et séparation dans les automates quantitatifs déterministes en histoire

Les automates déterministes en histoire sont un modèle intermédiaire entre le déterminisme et le non-déterminisme, qui profite d'une partie du pouvoir du non-déterminisme sans perdre toutes les propriétés algorithmiques du déterminisme. Ils sont particulièrement utiles pour résoudre des problèmes de synthèse, représentés comme des jeux. Les problèmes algorithmiques tels que l'inclusion, l'universalité en particulier ont tendance à être plus faciles pour les automates déterministes en histoire que pour les automates non-déterministes. Dans ce projet, nous nous demandons dans quelle mesure c'est aussi le cas pour les automates quantitatifs déterministes en histoire.

L'étudiant étudiera la complexité des problèmes d'universalité, d'inclusion et de séparation sur des automates déterministes d'histoire quantitative, à la fois à la recherche d'algorithmes efficaces et de bornes inferieures.

English version:

Universality, inclusion and separation in quantitative history-deterministic automata

History-deterministic automata are an intermediate model between determinism and nondeterminism, which enjoy some of power of nondeterminsm without losing all of the algorithmic properties of determinism. They are particularly useful for solving synthesis problems, represented as two-player games. Algorithmic problems such as inclusion, universality in particular tend to be easier for history-deterministic than nondeterministic automata. In this project, we ask to what extent this is also the case for history-deterministic quantitative automata.

The student will study the complexity of universality, inclusion and separation problems on quantitative history-deterministic automata, both looking for efficient algorithms and hardness results.

There will be games, algorithms and automata.